class Solution {
public:
    bool checkcol[9][10];
    bool checkdrow[9][10];
    bool gird[3][3][10];
    void solveSudoku(vector<vector<char>>& board) {

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {

                if (board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    checkdrow[i][num] = checkcol[j][num] =
                        gird[i / 3][j / 3][num] = true;
                }
            }
        }

        dfs(board);
    }

    bool dfs(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                // int num = board[i][j] - '0';
                if (board[i][j] == '.') {

                    for (int key = 1; key <= 9; key++) {

                        if (!checkdrow[i][key] && !checkcol[j][key] &&
                            !gird[i / 3][j / 3][key]) {
                            board[i][j] = key + '0';

                            checkcol[j][key] = checkdrow[i][key] =
                                gird[i / 3][j / 3][key] = true;
                            if (dfs(board) == true)
                                return true;

                            checkcol[j][key] = checkdrow[i][key] =
                                gird[i / 3][j / 3][key] = false;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
};